package com.mlh.skill;

/**
 * @author 缪林辉
 * @date 2024/7/5 11:27
 * @DESCRIPTION
 */
//给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。
// 假设 nums 只有 一个重复的整数(但重复多少次不知道) ，返回 这个重复的数 。
// 你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。

//输入：nums = [1,3,4,2,2,2]
// 输出：2
public class 寻找重复数 {
    //力扣题解
    //「二分查找」的思路是先猜一个数（搜索范围 [left..right] 里位于中间的数 mid），然后统计原始数组中 小于等于 mid 的元素的个数 count：
    // 如果 count 严格大于 mid。根据 抽屉原理，重复元素就在区间 [left..mid] 里；
    // 否则，重复元素可以在区间 [mid + 1..right] 里找到，其实只要第 1 点是对的，这里肯定是对的，但要说明这一点，需要一些推导，我们放在最后说。
    //抽屉原理：把 10 个苹果放进 9 个抽屉，至少有一个抽屉里至少放 2 个苹果
    public int method1(int[] nums) {
        if(nums.length<=2){
            return nums[0];
        }
        int right=nums.length-1,left=1;
        while (left<right){
            int mid=left+(right-left)/2;
            int count=0;
            for (int i = 0; i < nums.length; i++) {
                if(nums[i]<=mid){
                    count++;
                }
            }
            if(count>mid){
                right=mid;//如果count>mid  mid也可能是那个重复的元素 因此 right=mid
            }else{
                left=mid+1;//如果count<mid  mid不可能是那个重复的元素 因此 left=mid+1
            }
        }
        return right;
    }

    public int practice(int[]nums){
        if(nums.length<=2){
            return nums[0];
        }
        int mid,left=1,right=nums.length-1;
        while(left<right){
            mid=(left+right)/2;
            int count=0;
            for (int i = 0; i < nums.length; i++) {
                // 这里必须是nums[i]<=mid 去找小于或等于mid 的元素数量，如果是大于的话后面的判断都需要去对应修改
                if(nums[i]<=mid){
                    count++;
                }
            }
            if(count>mid){
               right=mid;
            }else{
                left=mid+1;
            }
        }
        return right;
    }
}
